package com.gitee.wsl.text.dfa

import com.gitee.wsl.collections.delegate.DelegatingMutableMap
import com.gitee.wsl.ext.string.charAt
import com.gitee.wsl.func.filter.Filter


/**
 * DFA（Deterministic Finite Automaton 确定有穷自动机）
 * DFA单词树（以下简称单词树），常用于在某大段文字中快速查找某几个关键词是否存在。<br></br>
 * 单词树使用group区分不同的关键字集合，不同的分组可以共享树枝，避免重复建树。<br></br>
 * 单词树使用树状结构表示一组单词。<br></br>
 * 例如：红领巾，红河构建树后为：<br></br>
 * 红                    <br></br>
 * /      \                 <br></br>
 * 领         河             <br></br>
 * /                            <br></br>
 * 巾                            <br></br>
 * 其中每个节点都是一个WordTree对象，查找时从上向下查找。<br></br>
 *
 * @author Looly
 */
class WordTree : DelegatingMutableMap<Char, WordTree>(mutableMapOf()) {
    /**
     * 单词字符末尾标识，用于标识单词末尾字符
     */
    private val endCharacterSet = HashSet<Char>()

    /**
     * 字符过滤规则，通过定义字符串过滤规则，过滤不需要的字符，当accept为false时，此字符不参与匹配
     */
    private var charFilter: Filter<Char> = Filter{ ch: Char -> StopChar.isNotStopChar(ch) }

    //--------------------------------------------------------------------------------------- Constructor start
    /**
     * 设置字符过滤规则，通过定义字符串过滤规则，过滤不需要的字符<br></br>
     * 当accept为false时，此字符不参与匹配
     *
     * @param charFilter 过滤函数
     * @return this
     * @since 5.2.0
     */
    fun setCharFilter(charFilter: Filter<Char>): WordTree {
        this.charFilter = charFilter
        return this
    }

    //------------------------------------------------------------------------------- add word
    /**
     * 增加一组单词
     *
     * @param words 单词集合
     * @return this
     */
    fun addWords(words: Collection<String>): WordTree {
        for (word in words) {
            addWord(word)
        }
        return this
    }

    /**
     * 增加一组单词
     *
     * @param words 单词数组
     * @return this
     */
    fun addWords(vararg words: String): WordTree {
        words.forEach { addWord(it) }
        return this
    }

    /**
     * 添加单词，使用默认类型
     *
     * @param word 单词
     * @return this
     */
    fun addWord(word: String): WordTree {
        val charFilter = this.charFilter
        var parent: WordTree? = null
        var current: WordTree = this
        var child: WordTree?
        var currentChar = 0.toChar()
        val length: Int = word.length
        for (i in 0..<length) {
            currentChar = word.charAt(i)
            if (charFilter(currentChar)) { //只处理合法字符
                child = current.get(currentChar)
                if (child == null) {
                    //无子类，新建一个子节点后存放下一个字符
                    child = WordTree()
                    current.put(currentChar, child)
                }
                parent = current
                current = child
            }
        }
        parent?.setEnd(currentChar)
        return this
    }

    //------------------------------------------------------------------------------- match
    /**
     * 指定文本是否包含树中的词
     *
     * @param text 被检查的文本
     * @return 是否包含
     */
    fun isMatch(text: String): Boolean {
        return null != matchWord(text)
    }

    /**
     * 获得第一个匹配的关键字
     *
     * @param text 被检查的文本
     * @return 匹配到的关键字
     */
    fun match(text: String): String? {
        val foundWord = matchWord(text)
        return foundWord?.toString()
    }

    /**
     * 获得第一个匹配的关键字
     *
     * @param text 被检查的文本
     * @return 匹配到的关键字
     * @since 5.5.3
     */
    fun matchWord(text: String): FoundWord? {
        return matchAllWords(text, 1)?.get( 0)
    }

    //------------------------------------------------------------------------------- match all
    /**
     * 找出所有匹配的关键字
     *
     * @param text 被检查的文本
     * @return 匹配的词列表
     */
    fun matchAll(text: String): List<String?> {
        return matchAll(text, -1)
    }

    /**
     * 找出所有匹配的关键字
     *
     * @param text 被检查的文本
     * @return 匹配的词列表
     * @since 5.5.3
     */
    fun matchAllWords(text: String): List<FoundWord>? {
        return matchAllWords(text, -1)
    }

    /**
     * 找出所有匹配的关键字
     *
     * @param text  被检查的文本
     * @param limit 限制匹配个数
     * @return 匹配的词列表
     */
    fun matchAll(text: String, limit: Int): List<String?> {
        return matchAll(text, limit, false, false)
    }

    /**
     * 找出所有匹配的关键字
     *
     * @param text  被检查的文本
     * @param limit 限制匹配个数
     * @return 匹配的词列表
     * @since 5.5.3
     */
    fun matchAllWords(text: String, limit: Int): List<FoundWord>? {
        return matchAllWords(text, limit, false, false)
    }

    /**
     * 找出所有匹配的关键字<br></br>
     * 密集匹配原则：假如关键词有 ab,b，文本是abab，将匹配 [ab,b,ab]<br></br>
     * 贪婪匹配（最长匹配）原则：假如关键字a,ab，最长匹配将匹配[a, ab]
     *
     * @param text           被检查的文本
     * @param limit          限制匹配个数
     * @param isDensityMatch 是否使用密集匹配原则
     * @param isGreedMatch   是否使用贪婪匹配（最长匹配）原则
     * @return 匹配的词列表
     */
    fun matchAll(text: String, limit: Int, isDensityMatch: Boolean, isGreedMatch: Boolean): List<String> {
        val matchAllWords = matchAllWords(text, limit, isDensityMatch, isGreedMatch)
        return matchAllWords.map { it.toString() }
        //return CollUtil.map(matchAllWords, { obj: FoundWord? -> obj.toString() }, true)
    }

    /**
     * 找出所有匹配的关键字<br></br>
     * 密集匹配原则：假如关键词有 ab,b，文本是abab，将匹配 [ab,b,ab]<br></br>
     * 贪婪匹配（最长匹配）原则：假如关键字a,ab，最长匹配将匹配[a, ab]
     *
     * @param text           被检查的文本
     * @param limit          限制匹配个数
     * @param isDensityMatch 是否使用密集匹配原则
     * @param isGreedMatch   是否使用贪婪匹配（最长匹配）原则
     * @return 匹配的词列表
     * @since 5.5.3
     */
    fun matchAllWords(text: String, limit: Int, isDensityMatch: Boolean, isGreedMatch: Boolean): List<FoundWord> {
        val foundWords = ArrayList<FoundWord>()
        var current: WordTree? = this
        val length: Int = text.length
        val charFilter = this.charFilter
        //存放查找到的字符缓存。完整出现一个词时加到findedWords中，否则清空
        val wordBuffer = StringBuilder()
        val keyBuffer = StringBuilder()
        var currentChar: Char
        var i = 0
        while (i < length) {
            wordBuffer.setLength(0)
            keyBuffer.setLength(0)
            for (j in i..<length) {
                currentChar = text.charAt(j)
                //				Console.log("i: {}, j: {}, currentChar: {}", i, j, currentChar);
                if (!charFilter(currentChar)) {
                    if (wordBuffer.isNotEmpty()) {
                        //做为关键词中间的停顿词被当作关键词的一部分被返回
                        wordBuffer.append(currentChar)
                    } else {
                        //停顿词做为关键词的第一个字符时需要跳过
                        i++
                    }
                    continue
                } else if (!current!!.containsKey(currentChar)) {
                    //非关键字符被整体略过，重新以下个字符开始检查
                    break
                }
                wordBuffer.append(currentChar)
                keyBuffer.append(currentChar)
                if (current.isEnd(currentChar)) {
                    //到达单词末尾，关键词成立，从此词的下一个位置开始查找
                    foundWords.add(FoundWord(keyBuffer.toString(), wordBuffer.toString(), i, j))
                    if (limit > 0 && foundWords.size >= limit) {
                        //超过匹配限制个数，直接返回
                        return foundWords
                    }
                    if (!isDensityMatch) {
                        //如果非密度匹配，跳过匹配到的词
                        i = j
                        break
                    }
                    if (!isGreedMatch) {
                        //如果懒惰匹配（非贪婪匹配）。当遇到第一个结尾标记就结束本轮匹配
                        break
                    }
                }
                current = current[currentChar]
                if (null == current) {
                    break
                }
            }
            current = this
            i++
        }
        return foundWords
    }

    //--------------------------------------------------------------------------------------- Private method start
    /**
     * 是否末尾
     *
     * @param c 检查的字符
     * @return 是否末尾
     */
    private fun isEnd(c: Char): Boolean {
        return this.endCharacterSet.contains(c)
    }

    /**
     * 设置是否到达末尾
     *
     * @param c 设置结尾的字符
     */
    private fun setEnd(c: Char) {
       this.endCharacterSet.add(c)
    }

    /**
     * 清除所有的词,
     * 此方法调用后, wordTree 将被清空
     * endCharacterSet 也将清空
     */

    override fun clear() {
        super.clear()
        this.endCharacterSet.clear()
    }
//--------------------------------------------------------------------------------------- Private method end

}
